#include "pwext.hpp"
#include <list>
#include <map>
#include <stdint.h>
#include <stdio.h>
#include <unistd.h>

// [[ex03ce]]
// DEBUG descr A simple LRU buffer cache written with the holds.
class cache;
class buffer : protected pw::hold
{
	friend class cache;
public:
	buffer(cache *owner) :
		valid_(false), cache_(owner)
	{ }

	char payload_[1024]; // the data in the buffer

	int32_t get_id() const
	{
		return id_;
	}

	void disk_ready()
	{
		pw::lockmutex lm(ready_);
		valid_ = true;
		ready_.broadcast();
	}

	void wait_until_valid()
	{
		pw::lockmutex lm(ready_);
		while(!valid_)
			ready_.wait();
	}

	// in real code release_buffer() definition must go
	// after cache is defined
	// DEBUG getfrom buffer::release_buffer
	void release_buffer();
	// DEBUG endget

protected:
	// position in the LRU list
	std::list<buffer *>::iterator lru_; 
	// used to signal the completion of disk ops, also
	// contains the mutex used to access the buffer
	pw::pmcond ready_; 
	// location of this buffer on disk (block number)
	int32_t id_; 
	// flag: the contents has been loaded from disk
	bool valid_; 
	// cache where it belongs
	cache *cache_; 
};

// just an interface, the internal implementation is
// not important here
class disk_driver
{
public:
	virtual ~disk_driver();
	// initiate a disk read operation, they may be
	// performed asynchronously in separate thread(s) or
	// synchronously in this thread, and will report the
	// completion by calling buf->disk_ready(); the read
	// address is obtained via buf->get_id()
	virtual void initiate_read(buffer *buf) = 0;
};

class cache : public pw::hold
{
	friend class buffer;
public:
	cache(disk_driver *disk, int limit = 1000) :
		disk_(disk), limit_(limit), freesem_(0)
	{ }

	// Makes sure that buffers are not used any more
	// before destroying them. But at this point there
	// must be no new get_buffer() requests.
	~cache()
	{
		freesem_.wait(idmap_.size());

		lru_list::iterator lit;
		for (lit = lrulist_.begin(); 
				lit != lrulist_.end(); ++lit)
			delete (*lit);
	}

	// Return a buffer with the given id, reading it from
	// the disk if necessary. The buffer is returned with
	// a hold on it.  After the caller is done with
	// copying the data out of the buffer, it must call
	// release_buffer(buf) May return 0 if the cache is
	// being destroyed.
	buffer *get_buffer(int32_t id)
	{
		buffer *buf = locate_buffer(id);
		if (buf == 0)
			return 0;
		buf->wait_until_valid();
		return buf;
	}

protected:
	// Release a hold on a buffer and bump it in the LRU
	// order
	void release_buffer(buffer *buf)
	{
		pw::lockmutex lm(mutex_);
		touch_l(buf);
		if (buf->release() == 0)
			freesem_.signal();
	}

	// The underlying implementation of finding or
	// creating a buffer.  Returns a buffer with a hold
	// on it, but not necessarily valid.  If the buffer
	// is not valid yet, the read on it will be already
	// initiated.  May return 0 if the cache is being
	// destroyed.
	buffer *locate_buffer(int32_t id)
	{
		buffer *buf;
		{
			pw::lockmutex lm(mutex_);
			
			id_map::iterator iit = idmap_.find(id);
			if (iit != idmap_.end()) { // already in the cache
				// buffer is already in the cache
				buf = iit->second;
				buf->acquire();
				touch_l(buf);
				return buf;
			}

			if (idmap_.size() >= limit_) {
				{
					pw::unlockmutex ul(mutex_);
					freesem_.wait();
				}
				buf = discard_l();
			} else
				buf = new buffer(this);

			if (buf == 0)
				return 0;
				
			buf->id_ = id;
			idmap_[id] = buf;
			buf->lru_ = lrulist_.insert(lrulist_.end(), buf);
			buf->acquire();
		}
		disk_->initiate_read(buf); // with mutex released !
		return buf;
	}

	// Bump the buffer in the LRU order, mutex already
	// locked
	void touch_l(buffer *buf)
	{
		lrulist_.erase(buf->lru_);
		buf->lru_ = lrulist_.insert(lrulist_.end(), buf);
	}

	// Discard the contents of the least recently used
	// buffer with no holds, to make space for a new one,
	// clear and return this buffer.  Expects mutex_ to
	// be already locked. The caller must ensure that
	// such a buffer is available, by decreasing freesem_
	// before calling.
	buffer *discard_l()
	{
		lru_list::iterator lit;
		for (lit = lrulist_.begin(); 
				lit != lrulist_.end(); ++lit) {
			buffer *buf = *lit;
			if (buf->get_hold_count() == 0) {
				// found the oldest unused buffer
	// DEBUG {
				fprintf(stderr, "buffer at %d discarded\n", buf->get_id());
	// DEBUG }
				idmap_.erase(buf->id_);
				lrulist_.erase(buf->lru_);
				buf->valid_ = false;
				return buf;
			}
		}
		return 0; // should never happen
	}

	pw::pmutex mutex_;
	disk_driver *disk_;
	int limit_;
	// count of buffers without a hold in the cache
	pw::semaphore freesem_; 

	typedef std::map<int32_t, buffer *> id_map;
	typedef std::list<buffer *> lru_list;

	id_map idmap_;
	lru_list lrulist_;
};
// DEBUG move buffer::release_buffer
	void /*DEBUG{*/buffer::/*}DEBUG*/release_buffer()
	{
		cache_->release_buffer(this);
	}
// DEBUG endmove buffer::release_buffer
// END

// DEBUG {

pw::semaphore ready(0);
pw::event startev;

class bg_reader : public pw::pwthread
{
public:
	bg_reader(buffer *buf) :
		pw::pwthread(true) /* autofree */, buf_(buf)
	{ }

	void *execute()
	{
		usleep(100*1000);
		fprintf(stderr, "buffer at %d read in background\n", buf_->get_id());
		buf_->disk_ready();
		return 0;
	}
	buffer *buf_;
};

disk_driver::~disk_driver()
{ }

class my_disk : public disk_driver
{
public:
	virtual ~my_disk()
	{ }

	virtual void initiate_read(buffer *buf)
	{
		if (buf->get_id() % 2 == 0) {
			usleep(100*1000);
			fprintf(stderr, "buffer at %d read in foreground\n", buf->get_id());
			buf->disk_ready();
		} else {
			bg_reader *reader = new bg_reader(buf);
			reader->start();
		}
	}
};

my_disk dsk;
cache mc(&dsk, 2);

class reader : public pw::pwthread
{
public:
	reader()
	{ 
		start();
	}
	~reader()
	{
		join();
	}

	void *execute()
	{
		// ready.signal(1);
		// startev.wait();
		for (int i = 0; i < 5; i++) {
			buffer *buf = mc.get_buffer(i);
			fprintf(stderr, "%p got buffer at %d\n", this, buf->get_id());
			buf->release_buffer();
		}
		return 0;
	}
};

int main()
{
	startev.reset();
	{
		reader r1, r2, r3, r4;
		// ready.wait(4);
		// startev.signal();
	}
	return 0;
}
// DEBUG }
/* Sample output:

buffer at 0 read in foreground
0x7fff21246f90 got buffer at 0
0x7fff21246f40 got buffer at 0
0x7fff21246ef0 got buffer at 0
0x7fff21246ea0 got buffer at 0
buffer at 1 read in background
0x7fff21246f90 got buffer at 1
buffer at 0 discarded
0x7fff21246ef0 got buffer at 1
0x7fff21246ea0 got buffer at 1
0x7fff21246f40 got buffer at 1
buffer at 2 read in foreground
0x7fff21246f90 got buffer at 2
buffer at 1 discarded
0x7fff21246ef0 got buffer at 2
0x7fff21246ea0 got buffer at 2
0x7fff21246f40 got buffer at 2
buffer at 3 read in background
0x7fff21246f90 got buffer at 3
buffer at 2 discarded
0x7fff21246ef0 got buffer at 3
0x7fff21246ea0 got buffer at 3
0x7fff21246f40 got buffer at 3
buffer at 4 read in foreground
0x7fff21246f90 got buffer at 4
0x7fff21246ef0 got buffer at 4
0x7fff21246ea0 got buffer at 4
0x7fff21246f40 got buffer at 4

*/
